﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using MultiResolutioning.Interfaces;
using MultiResolutioning.Structures;

namespace MultiResolutioning.Collections
{
	/// <summary>
	/// Klasa implementuje kolekcje kopca.
	/// </summary>
	/// <typeparam name="T">Typ elementow.</typeparam>
	public class Heap<T> where T: ICollectionable, IComparable<T>
	{
		private readonly IList<T> list;

		/// <summary>
		/// Inicjalizuje nowa instancje klasy<see cref="Heap{T}" />.
		/// </summary>
		/// <param name="list">Lista.</param>
		/// <param name="count">Dlugosc listy.</param>
		public Heap(IList<T> list, int count)
		{
			this.list = list;
			Count = count;
			Heapify();
		}

		public int Count { get; private set; }

		/// <summary>
		/// Zdejmuje korzen.
		/// </summary>
		public T PopRoot()
		{
			if (Count == 0) throw new InvalidOperationException("Empty heap.");
			var root = list[0];
			SwapCells(0, Count - 1);
			list.RemoveAt(Count - 1);
			Count--;
			HeapDown(0);
			return root;
		}

		/// <summary>
		/// Czyta korzen.
		/// </summary>
		public T PeekRoot()
		{
			if (Count == 0) throw new InvalidOperationException("Empty heap.");
			return list[0];
		}

		/// <summary>
		/// Wstawia element.
		/// </summary>
		public void Insert(T e)
		{
			if (Count >= list.Count) list.Add(e);
			else list[Count] = e;
			Count++;
			HeapUp(Count - 1);
		}

		private void Heapify()
		{
			for (int i = Parent(Count - 1); i >= 0; i--)
			{
				HeapDown(i);
			}
		}

		/// <summary>
		/// Reorganizuje element.
		/// </summary>
		/// <param name="i">Indeks elementu.</param>
		public void Update(int i)
		{
			HeapUp(i);
			HeapDown(i);
		}

		private void HeapUp(int i)
		{
			T elt = list[i];
			while (true)
			{
				int parent = Parent(i);
				if (parent < 0 || elt.CompareTo(list[parent]) > 0) break;
				SwapCells(i, parent);
				i = parent;
			}
		}

		private void HeapDown(int i)
		{
			while (true)
			{
				int lchild = LeftChild(i);
				if (lchild < 0) break;
				int rchild = RightChild(i);

				int child = rchild < 0
					? lchild
				: list[rchild].CompareTo(list[lchild]) > 0 ? lchild : rchild;

				if (list[i].CompareTo(list[child]) < 0) break;
				SwapCells(i, child);
				i = child;
			}
		}

		private int Parent(int i) { return i <= 0 ? -1 : SafeIndex((i - 1) / 2); }

		private int RightChild(int i) { return SafeIndex(2 * i + 2); }

		private int LeftChild(int i) { return SafeIndex(2 * i + 1); }

		private int SafeIndex(int i) { return i < Count ? i : -1; }

		private void SwapCells(int i, int j)
		{
			T temp = list[i];
			list[i] = list[j];
			list[j] = temp;

			list[j].InCollectionIndex = j;
			list[i].InCollectionIndex = i;
		}
	}
}
